﻿#region License
/*

	Copyright (C) 2008 Oliver Charles, Daniel Hollander

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>.
	
*/
#endregion

using System;
using System.Collections;
using System.Collections.Generic;

namespace Overload.Collections
{
    /// <summary>
    /// Represents a queue that is ordered by priorities.
    /// </summary>
    /// <typeparam name="TItemType">The type of data that this queue will contain</typeparam>
    /// <typeparam name="TPriorityType">
    /// The type to represent the priorty of the item. Must implement <see cref="IComparable{T}"/>
    /// </typeparam>
    public sealed class PriorityQueue<TItemType, TPriorityType> : IEnumerable<TItemType>, ICollection
        where TPriorityType : IComparable<TPriorityType>
        where TItemType : class
    {
        internal struct HeapEntry
        {
            private readonly TItemType item;
            private readonly TPriorityType priority;

            public HeapEntry(TItemType item, TPriorityType priority)
            {
                this.item = item;
                this.priority = priority;
            }

            public TItemType Item
            {
                get { return item; }
            }

            public TPriorityType Priority
            {
                get { return priority; }
            }

            public override string ToString()
            {
                return item.ToString();
            }
        }
        public sealed class Enumerator : IEnumerator<TItemType>
        {
            #region IEnumerator Implementation

            /// <summary>
            /// Advances the enumerator to the next element of the collection.
            /// </summary>
            /// <returns>
            /// true if the enumerator was successfully advanced to the next element; false if the enumerator
            /// has passed the end of the collection.
            /// </returns>
            ///<exception cref="T:System.InvalidOperationException">
            /// The collection was modified after the enumerator was created.
            /// </exception>
            public bool MoveNext()
            {
                if (cursor < items.Length)
                    cursor++;

                return !(cursor == items.Length && items[cursor + 1].Item != null);
            }

            /// <summary>
            /// Sets the enumerator to its initial position, which is before the first element in the
            /// collection.
            /// </summary>]
            /// <exception cref="T:System.InvalidOperationException">
            /// The collection was modified after the enumerator was created.
            /// </exception>
            public void Reset()
            {
                cursor = -1;
            }

            /// <summary>
            /// Gets the current element in the collection.
            /// </summary>
            /// <returns>The current element in the collection.</returns>
            ///<exception cref="T:System.InvalidOperationException">
            /// The enumerator is positioned before the first element of the collection or after the last
            /// element, or The collection was modified after the enumerator was created.
            /// </exception>
            public TItemType Current
            {
                get
                {
                    if (cursor < 0 || cursor >= items.Length)
                        throw new InvalidOperationException();

                    return items[cursor].Item;
                }
            }

            /// <summary>
            /// Gets the current element in the collection.
            /// </summary>
            /// <returns>The current element in the collection.</returns>
            ///<exception cref="T:System.InvalidOperationException">
            /// The enumerator is positioned before the first element of the collection or after the last
            /// element, or The collection was modified after the enumerator was created.
            /// </exception>
            object IEnumerator.Current
            {
                get
                {
                    if (cursor < 0 || cursor >= items.Length)
                        throw new InvalidOperationException();

                    return items[cursor].Item;
                }
            }

            #endregion

            private readonly HeapEntry[] items;
            private int cursor;

            internal Enumerator(HeapEntry[] items)
            {
                this.items = items;
                Reset();
            }

            #region IDisposable Members

            public void Dispose()
            {
            }

            #endregion
        }

        private int count;
        private HeapEntry[] items;

        #region Constructors

        /// <summary>
        /// Initializes a new instance of the PriorityQueue class that is empty, and has the defualt initial
        /// capacity.
        /// </summary>
        public PriorityQueue() : this(15)
        {
        }

        /// <summary>
        /// Initializes a new instance of the PriorityQueue class that is empty, and his a specific initial
        /// capacity
        /// </summary>
        /// <param name="initialCapacity">The initial capacity of the queue</param>
        public PriorityQueue(int initialCapacity)
        {
            items = new HeapEntry[initialCapacity];
        }

        #endregion

        #region ICollection Implementation

        /// <summary>
        /// Gets the amount of items in this queue
        /// </summary>
        public int Count
        {
            get { return count; }
        }

        /// <summary>
        /// Copies this priority queue to a specified one dimensional array, starting at a specific index
        /// </summary>
        /// <param name="array">
        /// The one-dimensional <see cref="Array"/> that is the destination of the elements copied from the priority
        /// queue. The <see cref="Array"/> must have zero-based indexing.
        /// </param>
        /// <param name="index">The zero-based index in array at which copying begins.</param>
        public void CopyTo(Array array, int index)
        {
            items.CopyTo(array, index);
        }

        /// <summary>
        /// Copies this priority queue to a specified one dimensional array, starting at a specific index
        /// </summary>
        /// <param name="array">
        /// The one-dimensional <see cref="Array"/> that is the destination of the elements copied from the priority
        /// queue. The <see cref="Array"/> must have zero-based indexing.
        /// </param>
        /// <param name="index">The zero-based index in array at which copying begins.</param>
        public void CopyTo(TItemType[] array, int index)
        {
            for (int i = 0; i < items.Length; i++)
                array[i + index] = items[i].Item;
        }

        public object SyncRoot
        {
            get { return this; }
        }
  
        public bool IsSynchronized
        {
            get { return false; }
        }

        public IEnumerator GetEnumerator()
        {
            return new Enumerator(items);
        }

        #endregion

        #region Queue item manipulation

        public void Enqueue(TItemType item, TPriorityType priority)
        {
            if (items.Length < count + 1)
                Resize();

            HeapEntry newEntry = new HeapEntry(item, priority);
            items[count] = newEntry;
            BubbleUp(count);

            count++;
        }


        public TItemType Dequeue()
        {
            HeapEntry highestPriority = items[0];

            count--;
            items[0] = items[count];

            TrickleDown(0);

            return highestPriority.Item;
        }

        #endregion

        #region Private Helpers

        private void Resize()
        {
            HeapEntry[] newItems = new HeapEntry[items.Length + 10];
            items.CopyTo(newItems, 0);
            items = newItems;
        }

        private void TrickleDown(int index)
        {
            int childIndex = (index * 2) + 1;

            while (childIndex < count)
            {
                if (((childIndex + 1) < count) &&
                    (items[childIndex].Priority.CompareTo(items[childIndex + 1].Priority) == -1))
                {
                    childIndex++;
                }

                Swap(index, childIndex);

                index = childIndex;
                childIndex = (index * 2) + 1;
            }
            BubbleUp(index);
        }

        void BubbleUp(int index)
        {
            HeapEntry thisItem = items[index];

            while (index > 0)
            {
                int parentIndex = (index - 1) / 2;

                if (items[parentIndex].Priority.CompareTo(thisItem.Priority) == -1)
                    Swap(index, parentIndex);

                index = parentIndex;
            }
        }

        private void Swap(int index1, int index2)
        {
            HeapEntry old = items[index1];
            items[index1] = items[index2];
            items[index2] = old;
        }

        #endregion

        public bool Contains(TItemType point)
        {
            bool contains = false;
            for (int i = 0; i < count; i++)
                contains = items[i].Item.Equals(point);

            return contains;
        }

        public override string ToString()
        {
            return "Count = " + Count;
        }

        #region IEnumerable<TItemType> Members

        IEnumerator<TItemType> IEnumerable<TItemType>.GetEnumerator()
        {
            return new Enumerator(items);
        }

        #endregion
    }
}